package roman.algorithm;

import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.Random;
import java.util.Scanner;

public class GreedyClustering {
	Random rd = new Random(System.currentTimeMillis());
	int dataLength = 10000;
	double[] x;
	double[] y;
	int[] belongTo;
	int k = 4;
	LinkedList<Integer> centers = new LinkedList<Integer>();
	
	public void process() throws Exception{
		Scanner sc = new Scanner(new FileInputStream("testdata\\data0"));
		x = new double[dataLength];
		y = new double[dataLength];
		belongTo = new int[dataLength];
		int counter = 0;
		double dist = 0;
		double prevDist = 0;
		double distOuter = 0;
		int index = 0;
		int indexOuter = 0;

		while(sc.hasNext()){
			x[counter] = sc.nextDouble();
			y[counter] = sc.nextDouble();
			counter++;
		}
		int tmp = rd.nextInt(dataLength);
		centers.add(tmp);
		// find the points which maximize the smallest distance to points in the cluser;
		for(int i=1;i<k;i++){
			distOuter = Double.MIN_VALUE;
			loop:
			for(int j=0;j<dataLength;j++){
				prevDist = Double.MAX_VALUE;
				for(int tmpIndex : centers){
					if(tmpIndex==j)
						continue loop;
					dist = Math.sqrt((x[i]-x[tmpIndex])*(x[i]-x[tmpIndex])+(y[i]-y[tmpIndex])*(y[i]-y[tmpIndex]));
					if(prevDist>dist){
						prevDist=dist;
						index = j;
					}
				}
				if(distOuter<prevDist){
					distOuter = prevDist;
					indexOuter = index;
				}
			}
			centers.add(indexOuter);
		}
		output();
	}
	
	public void assign(){
		int index;
		double dist,odist;
		for(int i=0; i<dataLength; i++){
			index = 0;
			odist = Double.MAX_VALUE;
			for(int tmp : centers){
				dist = Math.sqrt((x[i]-x[tmp])*(x[i]-x[tmp])+(y[i]-y[tmp])*(y[i]-y[tmp]));
				if(odist > dist){
					index=tmp;
					odist = dist;
				}
			}
			belongTo[i]=index;
		}
	}
	
	public void output() throws IOException{
		assign();
		PrintWriter pw1 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_1")));
		PrintWriter pw2 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_2")));
		PrintWriter pw3 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_3")));
		PrintWriter pw4 = new PrintWriter( new BufferedWriter(new FileWriter("testdata\\kmeans_4")));
		
		for(int i=0; i<dataLength; i++){
			if(belongTo[i]==centers.get(0)){
				pw1.println("1"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[i]==centers.get(1)){
				pw2.println("2"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[i]==centers.get(2)){
				pw3.println("3"+" "+x[i]+" "+y[i]);
				continue;
			}
			if(belongTo[i]==centers.get(3)){
				pw4.println("4"+" "+x[i]+" "+y[i]);
				continue;
			}
		}
		pw1.flush();
		pw1.close();
		pw2.flush();
		pw2.close();
		pw3.flush();
		pw3.close();
		pw4.flush();
		pw4.close();
	}
	
	public static void main(String[] argv) throws Exception{
		GreedyClustering o = new GreedyClustering();
		o.process();
	}
}
